import java.util.List;

public class Main {
    /**
     * 黄金矿工
     *//*
    boolean[][] visit;
    int max;
    int m, n;

    public int getMaximumGold(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        max = 0;
        visit = new boolean[m][n];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] != 0) {
                    visit[i][j] = true;
                    dfs(grid, i, j, grid[i][j]);
                    visit[i][j] = false;
                }

            }
        }
        return max;
    }

    int[] dx = { 0, 0, -1, 1 };
    int[] dy = { 1, -1, 0, 0 };

    public void dfs(int[][] grid, int i, int j, int path) {
        max = Math.max(max, path);
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if (x >= 0 && x < m && y >= 0 && y < n && visit[x][y] == false && grid[x][y] != 0) {
                visit[x][y] = true;
                dfs(grid, x, y, path + grid[x][y]);
                visit[x][y] = false;
            }
        }
    }*/
    /**
     * 不同路径3
     */
   /* int step;
    int m, n;
    boolean[][] visit;
    int ret;

    public int uniquePathsIII(int[][] grid) {
        m = grid.length;
        n = grid[0].length;
        step = 0;
        ret = 0;
        int bx = 0;
        int by = 0;
        visit = new boolean[m][n];
        //统计0个的数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0)
                    step++;
                if (grid[i][j] == 1) {
                    bx = i;
                    by = j;
                }
            }
        }
        //将1 2 也纳入步数
        step += 2;
        visit[bx][by] = true;
        dfs(grid, bx, by, 1);
        return ret;
    }

    int[] dx = {0, 0, -1, 1};
    int[] dy = {-1, 1, 0, 0};

    public void dfs(int[][] grid, int i, int j, int count) {
        if (grid[i][j] == 2) {
            //到终点了
            if (step == count) ret++;
            return;
        }
        for (int k = 0; k < 4; k++) {
            int x = i + dx[k];
            int y = j + dy[k];
            if ( x >= 0 && x < m &&y >= 0 && y < n && visit[x][y] == false && grid[x][y] != -1){
                visit[x][y] = true;
                dfs(grid, x, y, count + 1);
                visit[x][y] = false;
            }
        }
    }*/

    /**
     * 图像渲染
     */
    /*class Solution {

        int color;
        int m, n;
        int target;
        public int[][] floodFill(int[][] image, int sr, int sc, int _color) {
            m = image.length;
            n = image[0].length;
            target = image[sr][sc];
            color = _color;
            if (image[sr][sc] == color) {
                return image;
            }
            image[sr][sc] = color;
            dfs(image, sr, sc);
            return image;
        }

        int[] dx = { 0, 0, -1, 1 };
        int[] dy = { -1, 1, 0, 0 };

        void dfs(int[][] image, int sr, int sc) {
            for (int k = 0; k < 4; k++) {
                int x = sr + dx[k];
                int y = sc + dy[k];
                if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == target) {
                    image[x][y] = color;
                    dfs(image, x, y);
                }

            }
        }
    }*/

    /**
     * 岛屿数量
     */
    /*class Solution {
        boolean[][] visit;
        int m, n;
        int[] dx = {0,0,-1,1};
        int[] dy= {1,-1,0,0};

        public int numIslands(char[][] grid) {
            int ret = 0;
            m = grid.length;
            n = grid[0].length;
            visit = new boolean[m][n];
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(!visit[i][j] && grid[i][j] == '1') {
                        ret++;
                        dfs(grid, i, j);
                    }
                }
            }
            return ret;
        }
        public void dfs(char[][] grid, int i, int j) {
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(x >=0 && x < m && y >=0 && y < n && !visit[x][y] && grid[x][y] == '1') {
                    visit[x][y] = true;
                    dfs(grid, x, y);
                }
            }
        }
    }*/

    /**
     * 岛屿的最大面积
     */
 /*   class Solution {

        boolean[][] visit;
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        int m;
        int n;
        int count;
        public int maxAreaOfIsland(int[][] grid) {
            int ret = 0;
            count = 0;
            m = grid.length;
            n = grid[0].length;
            visit = new boolean[m][n];
            for(int i = 0; i < m; i++) {
                for(int j =0; j < n; j++) {
                    if(grid[i][j] == 1) {
                        visit[i][j] = true;
                        count++;
                        dfs(grid,i,j);
                        if(count > ret) {
                            ret = count;
                        }
                        count = 0;
                    }
                }
            }
            return ret;
        }
        void dfs(int[][] grid,int i, int j) {
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(x >=0 && x < m && y >=0 && y < n && visit[x][y] == false && grid[x][y] == 1) {
                    count++;
                    visit[x][y] = true;
                    dfs(grid,x,y);
                }
            }
        }
    }*/

    /**
     * 被围绕的区域
     */
    /*class Solution {
        boolean[][] visit;
        int m,n;
        public void solve(char[][] board) {
            m = board.length;
            n = board[0].length;
            visit = new boolean[m][n];
            //将边界上的o修改成.
            for(int c = 0; c < n; c++){
                if(board[0][c] == 'O') {
                    dfs(board, 0,c);
                }
                if(board[m - 1][c] == 'O') {
                    dfs(board, m - 1, c);
                }
            }
            for(int r = 0; r < m ; r++){
                if(board[r][0] == 'O') {
                    dfs(board, r, 0);
                }
                if(board[r][n - 1] == 'O') {
                    dfs(board,r,n-1);
                }
            }
            for(int i = 0; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(board[i][j] == 'O') {
                        board[i][j] = 'X';
                    } else if(board[i][j] == '.') {
                        board[i][j] = 'O';
                    }

                }
            }
        }
        int[] dx = {0,0,-1,1};
        int[] dy = {-1,1,0,0};
        public void dfs(char[][] board, int i, int j ) {
            visit[i][j] = true;
            board[i][j] = '.';
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(x >=0 && x < m && y >=0 && y < n && visit[x][y] == false && board[x][y] == 'O') {
                    dfs(board,x,y);
                }
            }
        }
    }*/

    /**
     * 太平洋和大西洋的水流问题
     */
    /*class Solution {
        int m, n;
        public List<List<Integer>> pacificAtlantic(int[][] h) {
            m = h.length;
            n = h[0].length;
            boolean[][] pac = new boolean[m][n];
            boolean[][] atl = new boolean[m][n];
            //先处理太平洋
            for (int j = 0; j < n; j++) {
                dfs(h, 0, j, pac);
            }
            for (int i = 0; i < m; i++) {
                dfs(h, i, 0, pac);
            }
            //处理大西洋
            for (int j = 0; j < n; j++) {
                dfs(h, m - 1, j, atl);
            }
            for (int i = 0; i < m; i++) {
                dfs(h, i, n - 1, atl);
            }
            List<List<Integer>> ret = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (pac[i][j] && atl[i][j]) {
                        List<Integer> t = new ArrayList<>();
                        t.add(i);
                        t.add(j);
                        ret.add(t);
                    }
                }
            }
            return ret;
        }

        int[] dx = { 0, 0, -1, 1 };
        int[] dy = { 1, -1, 0, 0 };

        void dfs(int[][] h, int i, int j, boolean[][] check) {
            check[i][j] = true;
            int target = h[i][j];
            for(int k = 0; k < 4; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(x >=0 && x < m && y >=0 && y < n && h[x][y] >= target && check[x][y] == false) {
                    dfs(h,x,y,check);
                }
            }
        }
    }*/

    /**
     * 扫雷游戏
     */
    /*class Solution {
        int[] dx = {0,0,-1,1,-1,-1,1,1};
        int[] dy = {-1,1,0,0,-1,1,-1,1};
        int m,n;
        public char[][] updateBoard(char[][] board, int[] click) {
            m = board.length;
            n = board[0].length;
            int x = click[0];
            int y = click[1];
            if(board[x][y] == 'M') {
                board[x][y] = 'X';
                return board;
            }
            dfs(board,x, y);
            return board;
        }
        void dfs(char[][] board, int i, int j) {
            //统计下当前位置周围地雷个数
            int count = 0;
            for(int k = 0; k <8; k++) {
                int x = i + dx[k];
                int y = j + dy[k];
                if(x >=0 && x < m && y >=0 && y < n && board[x][y] == 'M') {
                    count++;
                }
            }
            if(count >0) {
                //说明周围有地雷
                board[i][j] = (char)('0' + count);
                return;
            } else {
                //没地雷
                board[i][j] = 'B';
                for(int k = 0; k <8; k++) {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if(x >=0 && x < m && y >=0 && y < n && board[x][y] == 'E') {
                        dfs(board,x,y);
                    }
                }
            }
        }
    }*/

    /**
     *衣橱整理
     */
   /* class Solution {
        int ret;
        int cnt;
        int m,n;
        boolean[][] visit;
        public int wardrobeFinishing(int _m, int _n, int _cnt) {
            m = _m;
            n = _n;
            visit = new boolean[m][n];
            cnt = _cnt;
            ret = 0;
            dfs(0,0);
            return ret;
        }

        void dfs(int i, int j) {
            ret++;
            visit[i][j] = true;
            if(i >= 0 && i < m && j + 1 >=0 && j + 1 < n && digit(i) + digit(j + 1) <= cnt && visit[i][j + 1] == false) {
                dfs(i,j+1);
            }
            if(i + 1 >= 0 && i + 1 < m && j  >=0 && j  < n && digit(i + 1) + digit(j) <= cnt && visit[i + 1][j] == false) {
                dfs(i + 1,j);
            }
        }
        int digit(int x) {
            int sum = 0;
            while(x > 0) {
                sum += x % 10;
                x = x / 10;
            }
            return sum;
        }
    }*/




}
